package fun.ticsmyc.dataStructure;

import fun.ticsmyc.tools.BinaryTreeTools;
import fun.ticsmyc.tools.TreeNode;
import org.junit.Test;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author Ticsmyc
 * @date 2020-11-04 20:06
 */
public class 二叉树序列化和反序列化 {


    /**
     * 根据先序遍历序列化二叉树。 以!分隔节点， #表示null节点
     * @param head
     * @return
     */
    public String serialByPre(TreeNode head){
        if(head ==null){
            return "#!";
        }
        String res = head.val +"!";
        res += serialByPre(head.left);
        res += serialByPre(head.right);
        return res;
    }

    public TreeNode reconByPreString(String preStr){
        String[] values = preStr.split("!");
        Deque<String> queue = new LinkedList<>();
        for (String value : values) {
            queue.offer(value);
        }
        return reconPreOrder(queue);
    }
    private TreeNode reconPreOrder(Deque<String> queue){
        String cur = queue.poll();
        if("#".equals(cur)){
            return null;
        }
        TreeNode head = new TreeNode(Integer.parseInt(cur));
        head.left = reconPreOrder(queue);
        head.right=reconPreOrder(queue);
        return head;
    }


    //使用层序遍历的方式序列化和反序列化
    public String serialByLevel(TreeNode root){
        if(root == null){
            return "#!";
        }
        StringBuilder sb = new StringBuilder();
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        sb.append(root.val +"!");
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if(cur.left!= null){
                sb.append(cur.left.val +"!");
                queue.offer(cur.left);
            }else{
                sb.append("#!");
            }
            if(cur.right != null){
                sb.append(cur.right.val +"!");
                queue.offer(cur.right);
            }else{
                sb.append("#!");
            }
        }
        return sb.toString();
    }


    public TreeNode reconByLevelString(String levelStr){
        String[] values = levelStr.split("!");
        int index =0 ;
        TreeNode head = generateNodeByString(values[index++]);
        Deque<TreeNode> queue = new LinkedList<>();
        if(head != null){
            queue.offer(head);
        }
        while(!queue.isEmpty()){
            TreeNode cur =queue.poll();
            cur.left = generateNodeByString(values[index++]);
            cur.right = generateNodeByString(values[index++]);
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right!= null){
                queue.offer(cur.right);
            }
        }
        return head;
    }
    private TreeNode generateNodeByString(String value){
        if("#".equals(value)){
            return null;
        }
        return new TreeNode(Integer.parseInt(value));
    }


    public String serialize(TreeNode root) {
        if(root ==null) return "#!";
        StringBuilder sb = new StringBuilder();
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offerLast(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.pollFirst();
            if(cur != null){
                sb.append(cur.val+"!");
                queue.offerLast(cur.left);
                queue.offerLast(cur.right);
            }else{
                sb.append("#!");
            }
        }
        return sb.toString();
    }
    public TreeNode deserialize(String d) {
        String[] data = d.split("!");
        int index =0;
        if("#".equals(data[index])){
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(data[index++]));
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if("#".equals(data[index])){
                cur.left = null;
            }else{
                cur.left = new TreeNode(Integer.parseInt(data[index]));
                queue.offer(cur.left);
            }
            index++;
            if("#".equals(data[index])){
                cur.right = null;
            }else{
                cur.right = new TreeNode(Integer.parseInt(data[index]));
                queue.offer(cur.right);
            }
            index++;
        }
        return root;
    }
    @Test
    public void test() {
        TreeNode head = new TreeNode(1);
        head.left = new TreeNode(2);
        head.right = new TreeNode(3);
        head.left.left = new TreeNode(4);
        head.left.right = new TreeNode(5);
        head.left.left.left = new TreeNode(7);
        head.right.left = new TreeNode(6);
//        head.right.left.left = new TreeNode(6);
//        head.right.right = new TreeNode(10);
//        head.right.right.left = new TreeNode(9);
//        head.right.right.right = new TreeNode(11);

        BinaryTreeTools.printTree(head);

        System.out.println("----------基于先序遍历序列化和反序列化----------");
        String s = serialByPre(head);
        System.out.println(s);

        TreeNode treeNode = reconByPreString(s);
        BinaryTreeTools.printTree(treeNode);
        System.out.println();

        System.out.println("----------基于层序遍历序列化和反序列化----------");
        String s1 = serialByLevel(head);
        String s2 = serialize(head);
        System.out.println(s1);
        System.out.println(s2);
        TreeNode treeNode1 = reconByLevelString(s1);
        TreeNode treeNode2 = deserialize(s2);
        BinaryTreeTools.printTree(treeNode1);
        BinaryTreeTools.printTree(treeNode2);

    }
}
